package club.worldbang.structures.linkedList.doubleLinked;

import club.worldbang.structures.linkedList.ILinkedList;

//循环双链表实现
public class LoopHeadDILinkedList<T> implements ILinkedList<T> {
	public DNode<T> head;// 不带数据的头结点

	public LoopHeadDILinkedList() {
		this.head = new DNode<>();// 初始化头结点
		this.head.next = head;
		this.head.prev = head;

	}

	public LoopHeadDILinkedList(T[] array) {
		this();
		if (array != null && array.length > 0) {
			DNode<T> p = new DNode<>(array[0]);
			head.next = p;
			head.prev = p;
			p.prev = head;
			p.next = head;

			int i = 1;
			while (i < array.length) {
				p.next = new DNode<>(array[i++], p, head);
				head.prev = p.next;
				p = p.next;
			}
		}
	}

	// 循环双链表后继指针指向自己说明是空链表
	@Override
	public boolean isEmpty() {
		return this.head.next == head;
	}

	@Override
	public int length() {
		int length = 0;
		DNode<T> p = this.head.next;
		while (p != this.head) {
			length++;
			p = p.next;
		}
		return length;
	}

	@Override
	public T get(int index) {
		if (index >= 0) {
			int j = 0;
			DNode<T> p = this.head.next;
			while (p != head && j < index) {
				j++;
				p = p.next;
			}
			if (p != head)
				return p.data;
		}
		return null;
	}

	@Override
	public T set(int index, T data) {
		if (data == null) {
			return null;
		}

		if (index >= 0) {
			int j = 0;
			DNode<T> p = this.head.next;

			while (p != head && j < index) {
				j++;
				p = p.next;
			}

			// 如果不是头结点
			if (p != head) {
				T old = p.data;
				p.data = data;

				return old;
			}
		}
		return null;
	}

	@Override
	public boolean add(int index, T data) {
		int size = length();
		if (data == null || index < 0 || index > size) {
			return false;
		}
		int j = 0;
		DNode<T> p = this.head;
		// 查询插入位置的node
		while (p.next != head && j < index) {
			p = p.next;
			j++;
		}
		// 创建插入结点
		DNode<T> q = new DNode<>(data, p, p.next);
		p.next = q;
		p.next.prev = q;

		return true;
	}

	// 尾部添加
	@Override
	public boolean add(T data) {
		if (data == null)
			return false;
		DNode<T> p = new DNode<>(data, this.head.prev, this.head);
		// 更新tail的指向
		this.head.prev.next = p;
		this.head.prev = p;
		return true;
	}

	@Override
	public T remove(int index) {
		T old = null;
		int size = length();

		if (index < 0 || index >= size)
			return old;

		int j = 0;
		DNode<T> p = this.head.next;

		while (p != head && j < index) {
			j++;
			p = p.next;
		}

		if (p != head) {
			old = p.data;
			p.prev.next = p.next;
			p.next.prev = p.prev;
		}

		return old;
	}

	@Override
	public boolean removeAll(T data) {
		boolean isRemove = false;

		if (data == null) {
			return isRemove;
		}

		DNode<T> p = this.head.next;
		while (p != head) {
			if (data.equals(p.data)) {
				p.prev.next = p.next;
				p.next.prev = p.prev;
				isRemove = true;
			}
			p = p.next;
		}

		return isRemove;
	}

	@Override
	public void clear() {
		this.head.prev = head;
		this.head.next = head;
	}

	@Override
	public boolean contains(T data) {

		if (data == null) {
			return false;
		}
		DNode<T> p = this.head.next;
		while (p != head) {
			if (data.equals(p.data)) {
				return false;
			}

			p = p.next;
		}

		return false;
	}

	@Override
	public String toString() {
		String str = "(";
		DNode<T> p = this.head.next;
		while (p != head) {
			str += p.data.toString();
			p = p.next;
			if (p != head)
				str += ", ";
		}
		return str + ")";
	}
}
